package 剑指offer;

import java.util.ArrayList;
import java.util.Arrays;

import org.junit.Test;

public class _57_2和为s的两个数字 {
	@Test
	public void tes() {
		int[][] sequence = findContinuousSequence1(9);
		for (int i = 0; i < sequence.length; i++) {		
			System.out.println(Arrays.toString(sequence[i]));
		}
	}
	/**
	 * 
	 *@time 2021年3月23日下午9:56:32
	 * 
	 *@param target
	 *@return int[][]
	 *
	 *@see 求和公式法
	 *设连续正整数序列的左边界 i和右边界 j ，则此序列的 元素和 target 等于 元素平均值
	 *为(i+j)/2 	
  	 *乘以 元素数量 (j - i + 1) ，即：target = ((i + j) / 2) *(j - i + 1);
  	 *可知这是一个一元二次方程
  	 *整理得：
  	 *		j^2+j-(2*target+i^2-i) = 0;
  	 *根据求和公式可得j的值
  	 *	j= (-1+sqrt(1+4*(2*target+i^2-i)))/2
  	 *
  	 *通过从小到大遍历左边界 i 来计算 以 i 为起始数字的连续正整数序列 。每轮中，由以上公式计算得到右边界 j ，
  	 *当 j满足以下两个条件时记录结果：
	 *j为 整数 ：符合题目所求「连续正整数序列」；
	 *i < j ：满足题目要求「至少含有两个数」；
	 *
	 *主要是对比toArray(T[] a)中a的长度和list中的元素个数size
	 *如果a.length>=size, 那么直接调用System.arraycopy
	 *方法将elementData中的元素拷贝到a中即可
	 *如果a.length<size, 那么需要 Arrays.copyOf方法进行拷贝, 
	 *创建一个长度为size的新数组接收elementData中的元素, 之前传入的数组a已经没用了
	 */
	public int[][] findContinuousSequence(int target) {
		int i = 1;
		double j= 2.0;
		ArrayList<int[]> list = new ArrayList<int[]>();
		while(i<j) {
			j = (-1+Math.sqrt(1+4*(2*target+(long)(i*i)-i)))/2;
			if ( i < j && j==(int)j) {
				int []ans  =new int[(int)j-i+1];
				for (int k = i; k <=(int)j; k++) {
					ans[k-i] = k;
				}
				list.add(ans);
			}
			i++;
		}
		//数组的长度指定为0或者指定为list.size()都可以. 
		//即使传入的数组长度不够也没关系, 会创建新数组
		//int[][]的长度指定为0或者指定为list.size()都可以. 
		return  list.toArray(new int[0][]);
    }
	/**
	 * 
	 *@time 2021年3月24日下午7:13:30
	 * 
	 *@param target
	 *@return int[][]
	 *
	 *@see滑动窗口思想
	 *左边界
	 *相较于上面的，这里的时间复杂度比较快
	 */
	public int[][] findContinuousSequence1(int target) {
		int i = 1,j = 2,sum = 3;
		ArrayList<int[]> res = new ArrayList<int[]>();
		while(i < j) {
			if(sum == target) {
				int []ans = new int[j-i+1];
				for (int k = i; k <= j; k++) {
					ans[k-i] = k;
				}
				res.add(ans);
			}
			if (sum > target) {
				sum -= i;
				i++;
			}else {
				j++;
				sum += j;
			}		
		}
		return res.toArray(new int[0][]);
	}

}
